DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2023.6

Reconfiguration of Polygonal Subdivisions via Recombination

Authors: Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, and Thomas Weighill

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

Motivated by the problem of redistricting, we study area-preserving reconfigurations of connected subdivisions of a simple polygon. A connected subdivision of a polygon ℛ, called a district map, is a set of interior disjoint connected polygons called districts whose union equals ℛ. We consider the recombination as the reconfiguration move which takes a subdivision and produces another by merging two adjacent districts, and by splitting them into two connected polygons of the same area as the original districts. The complexity of a map is the number of vertices in the boundaries of its districts. Given two maps with k districts, with complexity O(n), and a perfect matching between districts of the same area in the two maps, we show constructively that (log n)^O(log k) recombination moves are sufficient to reconfigure one into the other. We also show that Ω(log n) recombination moves are sometimes necessary even when k = 3, thus providing a tight bound when k = 3.

Cite as

Hugo A. Akitaya, Andrei Gonczi, Diane L. Souvaine, Csaba D. Tóth, and Thomas Weighill. Reconfiguration of Polygonal Subdivisions via Recombination. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.ESA.2023.6,
  author =	{A. Akitaya, Hugo and Gonczi, Andrei and Souvaine, Diane L. and T\'{o}th, Csaba D. and Weighill, Thomas},
  title =	{{Reconfiguration of Polygonal Subdivisions via Recombination}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.6},
  URN =		{urn:nbn:de:0030-drops-186598},
  doi =		{10.4230/LIPIcs.ESA.2023.6},
  annote =	{Keywords: configuration space, gerrymandering, polygonal subdivision, recombination}
}

Search Results

Documents authored by Weighill, Thomas

Reconfiguration of Polygonal Subdivisions via Recombination

Abstract

Cite as

Thanks for your feedback!

Could not send message